package LearnAlgorithm.f_字符串;
/*
3
aaa
12
aabaabaabaab
0

Test case #1
2 2
3 3
Test case #2 
2 2
6 2
9 3
12 4

 */
import java.util.ArrayList;
import java.util.Scanner;

public class p查找周期前缀NEXT数组的运用 {
	public static void main(String[] args) {
		String string = "abcabcabc";
		begin();
	}
	
	public static void begin() {
		Scanner scanner = new Scanner(System.in);
		ArrayList<String> arrayList = new ArrayList<String>();
		int caseNum = 1;
		while (true) {
			int n = scanner.nextInt();
			if (n == 0) {
				break;
			}
			String string = scanner.next();
			arrayList.add(string);
		}
		for (int i = 0; i < arrayList.size(); i++) {
			String currentString = arrayList.get(i);
			int len = currentString.length();
			int[] next = makeNext(currentString);
			boolean flag = false;
			System.out.println("Test case #" + (i + 1));
			for (int current = 2; current < next.length; current++) {//核心；利用next数组；从2开始是因为next[0] = -1;next[1] = 0是固定的
				int back = next[current];
				int segment = current - back;//segment是“current与back之间的间隙”(不是距离！因为没有+1，你可以自己画图！)
				if (current % segment == 0 && current / segment > 1) {//如果是周期，那么segment其实是周期的“1/n”，n = current / segment
					flag = true;
					System.out.println(current + " " + current / segment);
				}
			}
			if (!flag) {
				System.out.println("没有周期");
			}
			printArr(next);
			System.out.println();
		}
	}
	
	public static int[] makeNext(String string) {
		if (string == null || string.length() == 0) {
			return null;
		}
		int[] next = new int[string.length() + 1];
		char[] stringArr = string.toCharArray();
		int length = string.length();
		next[0] = -1;
		if (length == 1) {
			return next;
		}
		next[1] = 0;
		int currentIndex = 1;
		int value = next[currentIndex];
		while (currentIndex < length) {//这里不是currentIndex < length - 1
			if (value < 0 || stringArr[currentIndex] == stringArr[value]) {
				next[++currentIndex] = ++value;
			} else {
				value = next[value];
			}
		}
		return next;
	}
	
	public static void printArr(int[] arr) {
		System.out.print("[ ");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
}
